package main

import (
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
执行用时：4 ms, 在所有 Go 提交中击败了89.71%的用户
内存消耗：3.6 MB, 在所有 Go 提交中击败了74.66%的用户
 */
func reverseKGroup(head *ListNode, k int) *ListNode {

	dummy := &ListNode{Val: -1}
	dummy.Next = head

	for p := dummy; ; {
		q := p
		for i := 0; i < k && q != nil; i++ { q = q.Next }
		if q == nil { break }
		// 内部k个一组翻转
		a, b := p.Next, p.Next.Next
		for i := 0; i < k - 1; i++ {
			c := b.Next
			b.Next = a
			a, b = b, c
		}
		c := p.Next
		p.Next = a
		c.Next = b
		p = c
	}
	return dummy.Next
}

func main() {
	fmt.Println("Hello World!")
}
